#-*- encoding=UTF-8 -*-

"""
스킵 리스트 구현
"""


import sys;
import random;

MAX_KEY = sys.maxint;
MIN_KEY = -sys.maxint-1
class SkipList:
	class Node:
		def __init__(self, k=MIN_KEY, v=None):
			self.key = k;
			self.value = v;
			self.next = None;
			self.prev = None;
			self.below = None;
			self.above = None;

		def setNext(self, rhs):
			if (self.next == None):
				self.next = rhs
				rhs.prev = self;
			else:
				tmp = self.next;
				self.next = rhs;
				rhs.next = tmp;
				tmp.prev = rhs;
				rhs.prev = self;

		def setAbove(self, t):
			self.above = t;
			t.below = self;


	def __init__(self, default_height=3):
		self.height = default_height;
		self.clear();
	
	def clear(self):
		""" Remove all node and initialize the list"""
		self.minNode = SkipList.Node();
		self.maxNode = SkipList.Node(MAX_KEY, None);
		self.minNode.setNext(self.maxNode);
		for i in range(1, self.height):
			n = SkipList.Node();
			self.minNode.setAbove(n);
			self.minNode = n;
			n = SkipList.Node(MAX_KEY, None);
			self.maxNode.setAbove(n);
			self.maxNode = n;

	def _skipSearch(self, k):
		curr = self.minNode;
		while (curr.next and curr.next.key <= k ):
			curr = curr.next;
		while ( curr.below != None ):
			curr = curr.below;
			while (curr.next and curr.next.key <= k):
				curr = curr.next;
		return curr

	def _grow(self, n):
		a = SkipList.Node(n.key, None);
		n.setAbove(a);
		return a;
	
	def insert(self, k, v):
		p = self._skipSearch(k);
		if ( p.key == k ):
			p.value = v;
		else:
			new_node = SkipList.Node(k, v);
			p.setNext(new_node);
			p = new_node

		i = -1
		while( random.randint(0,1) == 1 ):
			i += 1;
			if i >= self.height:
				self.height += 1;
				s = SkipList.Node();
				self.minNode.setAbove(s);
				self.minNode = s;
				t = SkipList.Node(MAX_KEY, None);
				self.maxNode.setAbove(t);
				self.maxNode = t;
				self.minNode.setNext(self.maxNode);
				
			q = p.prev;
			while q.above == None:
				q = q.prev
				if ( q == None ) :
					return p;
				
			q = q.above;
			new_node = self._grow(p);
			q.setNext(new_node);
			p = new_node;

		return p;
		
	def find(self, k):
		p = self._skipSearch(k);
		if ( p.key == k):
			return (True, p);
		else:
			return (False, p);

	def insertToNext(self, k, v, to):
		new_node = SkipList.Node(k, v);
		to.setNext(new_node);
		return new_node;

	def printSkipList(self):
		s = self.minNode
		while (s.below != None):
			s = s.below;

		matrix =  [];
		p = s;
		while (s != None ):
			i = 0;
			nodes = ['   '] * self.height;
			while (p != None):
				if ( p.key == MIN_KEY):
					nodes[i] = 'MIN';
				elif (p.key == MAX_KEY):
					nodes[i] = 'MAX';
				else:
					nodes[i] = "%3s" % str(p.key);
				p = p.above;
				i += 1

			matrix.append(nodes);
			s = s.next
			p = s;
			
		t_matrix = [];
		for i in range(self.height) :
			tmp = []
			for m in matrix:
				tmp.append(m[i]);
			t_matrix.append(tmp);

		t_matrix.reverse();
		
		for row in t_matrix:
			print "-".join(row);
				

if __name__=="__main__":
	sl = SkipList(5);
	sl.insert(1, "node1");
	sl.insert(5, "node5");
	sl.insert(4, "node4");
	sl.insert(8, "node8");
	sl.insert(9, "node9");
	sl.insert(2, "node2");
	sl.printSkipList();
	